package org.liaohailong.helloworld.example;

/**
 * Author: liaohailong
 * Date: 2021/8/12
 * Time: 21:42
 * Description:
 **/
public class GG {
    // s1 s2 s3 三个字符串中，判断s3是否由s1 s2交错组成
    public static void checkIsCombined(){
        // true
        String s1 = "aabcc";
        String s2 = "dbbca";
        String s3 = "aadbbcbcac";

        // false
//        String s1 = "aabcc";
//        String s2 = "dbbca";
//        String s3 = "aadbbbaccc";

        boolean ok = isCombined(s1, s2, s3);
        System.out.println("ok = " + ok);
    }

    private static boolean isCombined(String s1, String s2, String s3) {
        int s1Pos = 0; // s1检查到的下标
        int s2Pos = 0; // s2检查到的下标

        int s3Pos = 0; // s3检查到的下标

        boolean checkS1 = true;

        while (s3Pos < s3.length()) {
            String s = checkS1 ? s1 : s2;
            int sPos = checkS1 ? s1Pos : s2Pos;
            int count = find(s3, s3Pos, s, sPos);
            if (count <= 0) return false;
            s3Pos += count;
            sPos += count;
            if (checkS1)
                s1Pos = sPos;
            else
                s2Pos = sPos;
            checkS1 = !checkS1;
        }

        return s1Pos == s1.length() && s2Pos== s2.length();
    }

    private static int find(String s3, int s3Pos, String s, int sPos) {
        char[] s3Arr = s3.toCharArray();
        char[] sArr = s.toCharArray();
        int count = 0;
        while (s3Arr[s3Pos] == sArr[sPos]) {
            s3Pos++;
            sPos++;
            count++;
            if (s3Pos >= s3Arr.length || sPos >= sArr.length) break;
        }
        return count;
    }
}
